• 算法乐园 主页 笔记 刷题




      Algorithm-learning-notes

      算法笔记+个人代码(菜,仅供参考)

      笔记未完成,正在更新

      已完成:数组、排序、链表、哈希表、栈和队列、二叉树、回溯、贪心、动态规划

      正在更新:图论、字符串、单调栈

      版本:2023-12-07

      点击开启黑夜模式:darkmode

      基础算法总结

      题目参考:https://www.programmercarl.com/

      Algorithm-learning-notes基础算法总结时空复杂度理论数组专题数组1:二分查找数组3:有序数组的平方数组4:长度最小的子数组|滑动窗口排序专题:1插入排序数组的插入排序排序插入排序优化:折半插入排序链表的插入排序2希尔排序3冒泡排序数组的冒泡排序链表的冒泡排序4快速排序5选择排序数组的选择排序:链表的选择排序6堆排序无脑递归版本:(空间复杂度偏高)奇妙循环版本:复杂度分析:(对于循环版本的代码)应用:合并K个升序链表7归并排序复杂度分析对数组归并排序对链表归并排序8基数排序复杂度分析对链表基数排序9外部排序查找专题顺序查找二分查找二分答案1:爱吃香蕉的珂珂二分答案2:使结果不超过阈值的最小除数二分答案3:完成旅途的最少时间二分答案4:每个小孩最多能分到多少糖果二分答案5:准时到达的列车最小时速二分答案6:在 D 天内送达包裹的能力二分答案7:分配给商店的最多商品的最小值二分答案8:袋子里最少数目的球二分答案9:制作 m 束花所需的最少天数二分答案10:可以到达的最远建筑二分答案11:可移除字符的最大数目二分答案12:水位上升的泳池中游泳链表专题链表1:移除链表元素链表2:设计链表链表3:反转链表链表4:两两交换链表中的节点链表5:删除链表的倒数第N个节点链表6:相交链表链表7:环形链表II*哈希表专题哈希查找分析哈希表1: 有效的字母异位词哈希表2:两个数组的交集哈希表3:快乐数哈希表4:两数之和哈希表5:四数相加II哈希表6:赎金信哈希表6.9:两数之和 II - 输入有序数组哈希表7:三数之和字符串专题字符串1:反转字符串字符串2:反转字符串II字符串3:替换空格字符串4:反转字符串中的单词字符串6:找出字符串中第一个匹配项的下标方法1:KMP算法方法2:Rabin-Karp算法字符串7:重复的子字符串字符串8:有效数字方法1:暴力if-else方法2:有限状态自动机方法3:正则表达式字符串9:验证IP地址字符串10:实现Trie(前缀树)字符串11:连接词字符串12:字符流栈和队列专题栈和队列4:有效的括号栈和队列5:删除字符串中的所有相邻重复项栈和队列6:逆波兰表达式求值栈和队列7:基本计算器栈和队列8:基本计算器II优先队列专题优先队列1:股票价格波动二叉树专题树的理论基础树的性质二叉树的性质满二叉树完全二叉树完全二叉树的编号问题平衡二叉树二叉树2.递归遍历二叉树3.非递归遍历先序遍历:后序遍历:中序遍历:*二叉树5:层序遍历二叉树6:翻转二叉树二叉树8:对称二叉树二叉树9:二叉树的最大深度二叉树10:二叉树的最小深度二叉树11:完全二叉树的节点个数方法1:二分查找+位运算方法2:寻找满二叉树二叉树12:平衡二叉树二叉树13:二叉树的所有路径二叉树15:左叶子之和二叉树16:找树左下角的值二叉树17:路径总和二叉树18:从中序与后序遍历序列构造二叉树, 从前序与中序遍历序列构造二叉树二叉树19:最大二叉树二叉树21:合并二叉树二叉树22:二叉搜索树中的搜索二叉树23:验证二叉搜索树二叉树24:二叉搜索树的最小绝对差二叉树25:二叉搜索树中的众数二叉树26:二叉树的最近公共祖先二叉树28:二叉搜索树的最近公共祖先二叉树29:二叉搜索树的插入操作二叉树30:删除二叉搜索树中的节点回溯专题回溯2:组合回溯4:组合总和III回溯5:电话号码的字母组合回溯7:组合总和回溯8:组合总和II回溯9:分割回文串回溯10:复原IP地址回溯11:子集回溯13:子集II回溯14:递增子序列回溯15:全排列回溯16:全排列II回溯19:重新安排行程回溯20:N皇后回溯21:解数独贪心专题贪心2:分发饼干贪心3:摆动序列贪心4:最大子数组和贪心6:买卖股票的最佳时机 II贪心7:跳跃游戏贪心8:跳跃游戏II贪心9:K次取反后最大化的数组和贪心11: 加油站贪心12:分发糖果贪心13:柠檬水找零贪心14:根据身高重建队列*贪心17:用最少数量的箭引爆气球*贪心18:无重叠区间贪心19:划分字母区间贪心20:合并区间贪心22:单调递增的数字贪心23:监控二叉树图论专题最小生成树:连接所有节点的最小费用prim普里姆算法Kruskal算法最短路径问题:Dijkstra算法Dijkstra算法优化:使用小根堆priority_queueFloyd算法Bellman-ford算法SPFA算法拓扑排序课程表课程表II图论1:统计点对的数目图论2:课程表IV图论3:所有可能的路径图论4:岛屿数量图论5:岛屿的最大面积图论6:飞地的数量图论9:太平洋大西洋水流问题图论10:最大人工岛图论11:单词接龙图论12:钥匙和房间图论16:冗余连接动态规划专题代码随想录的刷题顺序:动态规划3:爬楼梯动态规划4:使用最小花费爬楼梯动态规划6:不同路径动态规划7:不同路径II动态规划8:整数拆分动态规划9:不同的二叉搜索树0-1背包系列 13~17动态规划13:分割等和子集动态规划14:最后一块石头的重量II动态规划16:目标和动态规划17:一和零完全背包系列 19~26动态规划19:零钱兑换II动态规划21:组合总和IV动态规划23:零钱兑换动态规划24:完全平方数动态规划26:单词拆分打家劫舍问题29-31动态规划29:打家劫舍动态规划30:打家劫舍II动态规划31:打家劫舍III股票问题32-38动态规划32.买卖股票的最佳时机动态规划34.买卖股票的最佳时机II动态规划35.买卖股票的最佳时机III动态规划36:买卖股票的最佳时机IV动态规划37:买卖股票的最佳时机含冷冻期动态规划38:买卖股票的最佳时机含手续费子序列问题动态规划41:最长递增子序列动态规划42:最长连续递增序列动态规划43:最长公共子序列动态规划44:最长公共子序列动态规划45:不相交的线动态规划46:最大子序和动态规划47:判断子序列动态规划48:不同的子序列动态规划49:两个字符串的删除操作动态规划50:编辑距离动态规划52:回文子串动态规划53:最长回文子序列动态规划54:切披萨的方案数灵神的刷题顺序:动态规划:从记忆化搜索到递推198打家劫舍70. 爬楼梯746. 使用最小花费爬楼梯2466.统计构造好字符串的方案数213.打家劫舍 II拆分类动态规划343.整数拆分96.不同的二叉搜索树0-1背包和完全背包494. 目标和(0-1背包)解法1. 回溯(暴力)解法:可以1952ms踩线通过解法2:灵神的0-1背包记忆递归模板记忆递归模板解题解法3: 数组递推的动态规划解法322. 零钱兑换416. 分割等和子集1049.最后一块石头的重量II279. 完全平方数518. 零钱兑换 II377.组合总和IV474. 一和零879.盈利计划最长公共子序列1143.最长公共子序列72. 编辑距离583. 两个字符串的删除操作712. 两个字符串的最小ASCII删除和1458. 两个子序列的最大点积97. 交错字符串单调栈专题单调栈1:每日温度单调栈2:下一个更大元素I

      时空复杂度理论

      使用OΩΘ表示法,分别表示算法的效率上限(上界)、下限(下界)、和等限(确界),其数学上的具体定义见表

      记号定义含义
      Of(n)=O(g(n)) 若存在两个正常数cn0,使nn0时,f(n)cg(n)f(n)的渐进上限为g(n)
      Ωf(n)=Ω(g(n)) 若存在两个正常数cn0,使nn0时,f(n)cg(n)f(n)的渐进下限为g(n)
      Θf(n)=Θ(g(n)) 若存在正常数c1c2n0,使nn0时,c1g(n)f(n)c2g(n)f(n)的渐进确界为g(n)

      如果c>0,n0>0 (n0为整数),使对于nn0,有f(n)cg(n)

      那么,f(n)=O(g(n))

      例1: f(n)=2n2+3n+1

      c=6,n0=100n>100,有

      f(n)=2n2+3n+12n2+3n2+n2=6n2=cn2

      由定义可证f(n)=O(n2)

      例2: f(n)=nlog2n,证明f(n)=O(n1.02)

      c=1,n0=3n>3,有

      n>3log2n<n0.02

      f(n)=nlog2nnn0.02=n1.02

      由定义可证f(n)=O(n1.02)

      时间复杂度的量级比较:

      O(1)<O(log2n)<O(n)<O(n)<O(nlog2n)<O(n1.01)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

      对于空间复杂度

      S(n)=O(f(n)),其中n为问题的规模,f(n)为语句关于n所占存储空间的函数

      数组专题

      数组1:二分查找

      手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找(参考视频)

      leetcode704

      左闭右闭模板:

      注意四个细节:

      C++

      python:

      左闭右开模板:

      注意四个细节:

      C++:

      python:

      递归版二分查找

      数组3:有序数组的平方

      双指针法经典题目 | LeetCode:977.有序数组的平方(参考视频)

      leetcode977

      推荐双指针法,由绝对值最小的数开始往两边遍历

      当然也可以由两边向中间遍历数组

      python:

      数组4:长度最小的子数组|滑动窗口

      leetcode209

      拿下滑动窗口! | LeetCode 209 长度最小的子数(参考视频)

      python:

      排序专题:

      数组排序:leetcode912

      单链表排序:leetcode148(测试用例很容易超时,matrix的面试题,当年我就没做出来😖)

      对链表进行插入排序:leetcode147(不容易超时)

      image-20230726124830123

      image-20231020150620423

      1插入排序

      支持数组和链表

      数组的插入排序排序

      空间复杂度O(1),因为只使用了常数个临时变量

      最好时间复杂度:O(n),对应于数组已经有序的情况

      最坏时间复杂度:O(n2),对应数组完全逆序的情况

      平均时间复杂度:O(n2)

      具有稳定性

      (在leetcode912提交会超时)

      插入排序优化:折半插入排序

      当遍历到第i个1元素时,[0,i-1]的所有元素时有序的,可以利用二分查找的方法找到插入位置

      然鹅, 时间复杂度没有质的飞跃

      空间复杂度O(1)

      最好时间复杂度:O(n),对应于数组已经有序的情况

      最坏时间复杂度:O(n2),对应数组完全逆序的情况

      平均时间复杂度:O(n2)

      具有稳定性

      (在leetcode912提交会超时)

      链表的插入排序

      空间复杂度:O(1),只额外开辟了常数级别的空间

      最好时间复杂度:O(n),对应于数组已经有序的情况

      最坏时间复杂度:O(n2),对应数组完全逆序的情况

      平均时间复杂度:O(n2)

      具有稳定性

      (在leetcode148提交会超时,leetcode147提交通过,16ms,9.3MB)

      2希尔排序

      仅支持数组,不适用链表

      先追求表中元素部分有序,再逐渐逼近全局有序

      每一轮都按照一个给定的间隔进行插入排序,这个间隔应当逐渐减少,最后必须为1

      以下的代码中, 步长(间隔)从n2开始递减,每次变为原来的12,直到变为1

      空间复杂度:O(1)

      时间复杂度:和增量序列d1,d2,d3,的选择有关,目前无法用数学手段证明确切的时间复杂度

      最坏时间复杂度O(n2),也就是取d=1的时候,这时候希尔排序退化为插入排序

      n在某个范围内时,可达O(n1.3)

      不具有稳定性,例如:

      原始序列: 65 49 49

      第一趟:d=2 49 49 65

      第一趟:d=1 49 49 65

      C++

      (在leetcode912提交通过,224ms,65MB)

      python

      (在leetcode912提交通过,1208ms,22MB)

      3冒泡排序

      数组的冒泡排序

      可用于数组和链表

      空间复杂度:O(1)

      时间复杂度

      最好情况(有序):O(n)

      最坏情况(逆序):O(n2)

      平均时间复杂度:O(n2)

      具有稳定性

      (在leetcode912提交会超时)

      链表的冒泡排序

      (在leetcode148提交会超时,leetcode147通过112ms,9.3MB)

      4快速排序

      最好空间复杂度:O(log2n)

      最坏空间复杂度:O(n)

      最好时间复杂度:O(nlog2n)

      最坏时间复杂度:O(n2)

      平均时间复杂度O(nlog2n)

      如果每次选中的枢轴将待排序序列划分为均匀的两个部分,则递归深度最小,算法效率最高

      若数组原本就有序或逆序,则快速排序性能最差

      算法不稳定

      (在leetcode912提交会超时)

      优化版:随机选取pivot+优化内部while循环

      (在leetcode912提交通过,172ms,64MB)

      关键:while循环优化

      nums[high]>pivot不取等,防止因为大量重复的数使得在这个循环就导致high一直减到等于low,递归树更加平衡

      5选择排序

      数组的选择排序:

      空间复杂度O(1)

      时间复杂度O(n2)

      不稳定,例如:主要原因是使用了swap函数,如果牺牲一些时间,整体后移所有元素以避免使用swap,算法可以变为稳定的

      原始序列 3 3 1

      排序后 1 3 3

      (在leetcode912提交会超时)

      链表的选择排序

      空间复杂度O(1)

      时间复杂度O(n2)

      具有稳定性

      (在leetcode148提交会超时,leetcode147通过,80ms,9.4MB)

      6堆排序

      只适用于数组

      堆排序利用大根堆,本质是按照节点序号(从1开始)存储在数组中的完全二叉树

      几个基本操作

      若完全二叉树中有n个节点,则

      若n个关键字序列L[1...n]满足下面某一条性质,则称为堆(Heap)

      如果下标从0开始,则:

      若完全二叉树中有n个节点,则

      无脑递归版本:(空间复杂度偏高)

      leetcode912通过,308ms,65MB

      奇妙循环版本:

      C++

      leetcode912通过,204ms,65MB

      python

      leetcode912通过,1708ms,21.88MB

      复杂度分析:(对于循环版本的代码)

      复杂度分析部分考虑下标从1开始

      二叉树高h=log2n+1

      i层最多有2i1个节点,只有第1~(h-1)层的节点才可能需要下坠处理,每次下坠最多对比2次,第i层节点下坠最多对比h-i次

      把整棵树调整为大根堆, 关键字对比次数:

      i=h112i12(hi)=i=h112i(hi)=j=1h12hjj=2hj=1h1j2j=2log2n+1(2h+12h1)2n2=4n

      所以建堆的过程中时间复杂度O(n)

      排序的过程中总共需要处理n-1个节点,每个节点最多需要下坠h-1层,时间复杂度O(nlog2n)

      总的时间复杂度O(nlog2n)

      空间复杂度O(1)

      堆排序不稳定,例如

      原始序列 1 2 2

      排序后 1 2 2

      应用:合并K个升序链表

      leetcode23

      利用小根堆的性质解决

      C++:

      7归并排序

      复杂度分析

      2路归并的归并树,形态上就是一棵倒立的二叉树

      二叉树的第h层最多有2h1个节点,若树高为h,满足n2h1

      h1=log2n

      n个元素进行二路归并排序,归并趟数=log2n

      每趟归并的时间复杂度O(n),算法的时间复杂度O(nlog2n)

      递归工作栈的空间复杂度为O(log2n),辅助数组的空间复杂度O(n)

      总的空间复杂度O(n)

      归并排序具有稳定性

      对数组归并排序

      C++

      leetcode912通过,312ms,67.1MB

      python

      leetcode912通过,1404ms,32.36MB

      对链表归并排序

      leetcode148通过,368ms,95.18MB

      8基数排序

      复杂度分析

      可以证明,基于比较的排序,时间复杂度不可能优于O(nlogn),基数排序不基于比较

      通常针对链表实现,假设长度为n的线性表中每个节点aj的关键字由d元组(kjd1,kjd2,kjd3,,kj1,kj0)组成

      其中 , 0kjir1(0j<n,0id1), r 称为基数

      空间复杂度 O(n)

      链表初始化时间复杂度 O(r) ,一趟分配的时间复杂度 O(n) ,一趟收集的时间复杂度 O(r) ,总共 d 趟,时间复杂度 O(d(n+r))

      对于leetcode148,105Node.val105,n[0,5×104]

      排序时加上105,保证所有数为正数,对于十进制数r=10,d不超过6

      所有该题时间复杂度O(n),空间复杂度O(n)

      基数排序是稳定的, 因为基你太稳

      对链表基数排序

      leetcode148通过,216ms,63.4MB

      9外部排序

      image-20231015110236652

      优化1:采用多路归并可以减少归并趟数,从而减少磁盘I/O(读写)次数

      r个初始归并段,做k路归并,则归并数可用k叉树表示

      k叉树的第h层最多有kh1个结点,则rkh1,归并趟数h1logkr

      k路平衡归并:

      1. 最多只能有k个段归并为一个;
      2. 每一趟归并中,若有 m 个归并段参与归并,则经过这一趟处理得到mk个新的归并段

      k=4的情况:

      image-20231015114623590

      多路归并带来的负面影响:

      1. k路归并时,需要开辟k个输入缓冲区,内存开销增加。
      2. 每挑选一个关键字需要对比关键字(k1)次,内部归并所需时间增加

      优化2:减少初始归并段r的数量

      生成初始归并段的方法:若总共有N条记录,内存工作区可以容纳L条记录,则初始归并段数量r=NL

      查找专题

      查找过程中的主要操作是关键字的比较,查找过程中的关键字的平均比较次数(平均查找长度ASL(Average search length))作为衡量一个查找算法效率高低的标准,ASL定义为:

      ASL=i=1nPiCi

      顺序查找

      对于长度为n的顺序表:

      ASL=1ni=1ni=n+12

      时间复杂度O(n)

      二分查找

      实现代码

      前提:查找表中所有记录是有序的(升序或降序)

      对二分查找有效性的证明:

      因为算法在top>bottom的条件下持续运行,只需证明在该条件下区间大小[bottom,top]是严格变小的

      1+top-bottom
      1+top-mid-1
      1+mid-bottom

      证明其一:

      bottom<top2bottom<bottom+1bottom<bottom+top2bottom<bottom+top2+1bottom<mid+11+topbottom>1+topmid1

      另一侧证明同理

      二分答案1:爱吃香蕉的珂珂

      leetcode875

      二分答案2:使结果不超过阈值的最小除数

      leetcode1283

      二分答案3:完成旅途的最少时间

      leetcode2187

      大佬的一行代码,出自灵神题解

      bisect用法

      二分答案4:每个小孩最多能分到多少糖果

      leetcode2226

      二分答案5:准时到达的列车最小时速

      leetcode1870

      二分答案6:在 D 天内送达包裹的能力

      leetcode1011

      二分答案7:分配给商店的最多商品的最小值

      leetcode2064

      根据贪心原则,一旦确定x,每个商店分配的商品数就应该尽可能靠近x,否则就可能存在一个比x更优的结果

      所以在x确定之后,能够分配的商店数量为sum(ceil(q/mid) for q in quantities)

      二分答案8:袋子里最少数目的球

      leetcode1760

      二分下界:每个袋子最少一个球,low=1

      二分上界:最坏的情况是不进行操作,开销为球最多的袋子中的球数,high=max(nums)

      假设已经确定开销为mid,球数为n的袋子至少需要操作ceil(n/mid)-1次,总开销为sum(ceil(n/mid)-1 for n in nums)

      二分答案9:制作 m 束花所需的最少天数

      leetcode1482

      二分答案10:可以到达的最远建筑

      leetcode1642

      二分答案11:可移除字符的最大数目

      leetcode1898

      二分答案12:水位上升的泳池中游泳

      leetcode778

      二分+dfs

       

      链表专题

      链表1:移除链表元素

      leetcode203

      使用虚拟头节点:

      C++

      不使用虚拟头节点:

      python

      链表2:设计链表

      leetcode707

      单向链表(使用虚拟头节点):

      链表3:反转链表

      leetcode206

      方法1:栈

      时间复杂度O(n),空间复杂度O(n)

      方法2:双指针

      时间复杂度O(n),空间复杂度O(1)

      方法3:递归

      时间复杂度O(n),空间复杂度O(n)

      链表4:两两交换链表中的节点

      leetcode24

      链表5:删除链表的倒数第N个节点

      leetcode19

      快慢指针法:先将右指针右移n个节点,再将左右指针一起右移,直到右指针的下一个位置为nullptr,此时左指针指向待删除节点的上一个位置

      链表6:相交链表

      leetcode160

      链表7:环形链表II*

      leetcode142

      快慢指针法:

      快指针一次移动2个节点,慢指针一次移动1个节点,移动完成后才检查二者是否相遇,两者相对速度1个节点,所以不会存在快指针越过慢指针而没有检测到的情况

      对于慢指针 t=a+b

      可以证明慢指针在圈里的路程不足一圈,不是t=a+b+k(b+c), 因为慢指针进入圈内时,快指针已经在圈内,慢指针要转完一圈,快指针就会转两圈,所以在慢指针转完一圈之前,快指针就会和慢指针相遇

      对于快指针 2t=a+b+n(b+c)

      所以a=(n-1)(b+c)+c

      让两个指针分别从头节点和相遇点出发,二者一定会在环的入口处相遇

      时间复杂度O(n), 空间复杂度O(1)

      C++:

      python:

      哈希表专题

      哈希查找分析

      装填因子α=nm

      二次探测、伪随机探测、再哈希法的平均查找长度是

      S1αln(1α)
      S11α

      在表中任选一个位置,不为空的概率为α,为空的概率为1α

      查找k个位置后结束,对应的概率为αk1(1α)

      查找失败的概率为

      k=1kαk1(1α)=11α

       

      查找关键字k的探测序列和插入关键字k的探测序列是相同的,假设k是第k+1个被插入到散列表中的关键字,则此前散列表的装填因子为im,查找k的探测次数的期望为11im。则查找成功的探测次数的期望为

      1ni=0n1mmi=mni=0n11mi=1αk=mn+1m1k1αmnm1xdx=1αlnmmn=1αln11α=1αln(1α)

      哈希表1: 有效的字母异位词

      leetcode242

      简单题,大佬们可以直接跳过

      用数组代替哈希表

      哈希表2:两个数组的交集

      leetcode349

      简单题,大佬们可以直接跳过

      python:

      哈希表3:快乐数

      leetcode202

      哈希表4:两数之和

      leetcode1

      经典好题

      C++:

      python:

      哈希表5:四数相加II

      leetcode454

      四个for循环O(n4)会超时

      两组两个for循环,配合哈希表可以通过,时间复杂度O(n2)

      哈希表6:赎金信

      leetcode383

      简单题,大佬们可以直接跳过

      python:

      哈希表6.9:两数之和 II - 输入有序数组

      leetcode167

      这一题是给下一题打基础用的

      推荐看灵神的视频

      C++:

      python:

      课后作业

      哈希表7:三数之和

      leetcode15

      这题不好做 😫

      C++:

      python:

      字符串专题

      字符串1:反转字符串

      leetcode344

      双指针交换就行

      C++:

      Javascript:

      字符串2:反转字符串II

      leetcode541

      字符串3:替换空格

      leetcode剑指offer05

      算法很简单,可以拿这个检验一下自己对库函数的熟悉程度

      Javascript:不用库函数

      直接调用库函数:

      python也有这个库函数:

      字符串4:反转字符串中的单词

      leetcode151

      JavaScript:

      大佬的调用内置函数解法:

      字符串6:找出字符串中第一个匹配项的下标

      leetcode28

      KMP算法的经典例题

      方法1:KMP算法

      next数组 样例1:

      aabaaf
      010120

      next数组 样例2:

      aabaaab
      0101223

      遍历的过程中,遍历next数组的指针指向下标为j处时,遇到不匹配,就回退到下标next[j-1]

      next[i]=k的含义是在needle中前i个字母的最大相同前后缀长度,即满足needle[0:k]==needle[i-k+1:i+1] (i-k+1>=k)的最大k值 (注: needle[a:b]的含义是needle字符串中下标>=a<b的子串)

      next数组的构造过程

      i指向后缀表的末尾,j指向前缀表的末尾,每轮循环需要判断前后缀表的末尾元素能否加入前后缀表中,也就是比较needle[i]needle[j]是否相等

      前缀表和后缀表等长,末尾元素加入前后缀表后,长度都是j+1

      初始化i=1j=0

      详细注释版 C++

      (细心的你会发现,构造next数组和匹配字符串过程代码是相似的)

      简洁优雅版 C++

      时间复杂度

      参考KMP算法-时间复杂度分析

      n是模式串haystack的长度,m是待匹配的字符串needle的长度

      计算next数组时的比较次数介于[m,2m]。 遍历比较的比较次数介于[n,2n],最坏情形形如T=“aaaabaaaab”,P=“aaaaa”。 所以算法时间复杂度时O(m+n).

      空间复杂度O(m)

      方法2:Rabin-Karp算法

      这个算法实际上就是哈希表,ChatGPT的解释:

      Rabin-Karp算法是一种字符串匹配算法,用于在一个文本串中查找一个模式串的出现位置。

      算法的基本思想是通过哈希函数将模式串和文本串的子串进行比较。首先计算模式串的哈希值,然后依次计算文本串中所有长度为模式串长度的子串的哈希值,并与模式串的哈希值进行比较。如果哈希值相同,再逐个比较子串和模式串的每个字符是否相同,直到找到完全匹配的子串或者遍历完所有子串。

      算法的优点是可以在平均情况下达到线性时间复杂度O(n+m),其中n是文本串的长度,m是模式串的长度。然而,在最坏情况下,算法的时间复杂度为O((n-m+1)m),即当哈希值的冲突比较多时,效率会下降。

      总结来说,Rabin-Karp算法通过哈希函数加速字符串匹配,适用于处理长文本串和短模式串的情况。它在实际应用中常被用于字符串搜索、文本编辑器等领域。

      字符串7:重复的子字符串

      leetcode459

      方法1:双指针

      方法2:转化为字符串匹配问题

      方法3:转化为字符串匹配问题,并利用KMP算法

      字符串8:有效数字

      leetcode65

      方法1:暴力if-else

      笨人的这段代码比较乱,建议去看方法2,更易理解

      0ms 5.8MB

      方法2:有限状态自动机

      参考文献

      1. 初始状态
      2. 符号位
      3. 整数部分
      4. 左侧有整数的小数点
      5. 左侧无整数的小数点(根据前面的第二条额外规则,需要对左侧有无整数的两种小数点做区分)
      6. 小数部分
      7. 字符 e
      8. 指数部分的符号位
      9. 指数部分的整数部分

      (图片出自力扣官方题解)

      image-20230812093747065

      最后只有cur==2||cur==3||cur==5||cur==8时返回true

      0ms 5.9MB

      方法3:正则表达式

      C++的正则表达式库

      正则表达式大全

      代码粘贴自评论区大佬

      正在表达式的构造耗时很长,所以建议采用第二段代码,避免重复构造

      1884ms,259.3MB

      12ms 9MB

      字符串9:验证IP地址

      正则表达式

      字符串10:实现Trie(前缀树)

      leetcode208

      字典树的经典例题

      字符串11:连接词

      leetcode472

      前缀树+记忆化搜索

      前缀树+DFS+记忆化搜索

      字符串12:字符流

      leetcode1032

      AC自动机的经典例题

      OI-wiki:AC自动机



       

      栈和队列专题

      栈是一种后进先出的数据结构(Last in, First out. LIFO)

      应用:括号匹配问题等

      队列是一种先进先出的数据结构(First in,First out. FIFO)

      应用:cpu资源的竞争问题、解决主机和外部设备速度不匹配的问题、电子商务系统中的缓冲队列

      优先队列:

      用堆实现,具备最高进先出(largest-in,first-out)的特点

      操作有查找、插入一个新元素和删除三种

      栈和队列4:有效的括号

      leetcode20

      相当基础的栈的应用

      栈和队列5:删除字符串中的所有相邻重复项

      leetcode1047

      栈和队列6:逆波兰表达式求值

      leetcode150

      以下为王道考研数据结构的笔记:栈在表达式求值中的应用

      序号表示各个运算符的执行顺序

      image-20230725205911577

      image-20230725210612767

      image-20230725213918526

      image-20230725222156240

      C++:

      栈和队列7:基本计算器

      leetcode224

      栈和队列8:基本计算器II

      leetcode227

      代码在上一题的基础上改了一下,可以支持对正负数的+-*/和括号运算

      优先队列专题

      优先队列1:股票价格波动

      leetcode2034

       

      二叉树专题

      树的理论基础

      树的性质

      度为m的树m叉树
      任意结点的度m任意结点的度m
      至少有一个结点的度 = m允许所有节点的度都 < m
      1. 树中的结点数等于所有结点的度数之和加1
      2. 度为m的树第i层至多有mi1个结点(i1
      3. 高度为hm叉树至多有mh1m1个结点,证明:
      m0+m1++mh1=mh1m1
      1. 高度为hm叉树至少有h个结点

        高度为h、度为m的树至少有h+m1个结点

      2. 具有n个结点的m叉树最小高度为logm(n(m1)+1),证明:

      高度最小的情况:所有结点都有m个孩子

      h1mh11m1<nmh1m1h
      mh1<n(m1)+1<mh
      h1<logm(n(m1)+1)<h
      hmin=logm(n(m1)+1)

      二叉树的性质

      设非空二叉树中度为0、1、2的结点个数分别是n0, n1, n2,树中结点总数为n

      (1)n0=n2+1
      (2)n=n0+n1+n2
      (3)n=n1+2n2+1(+1)

      (3)-(2)得到(1)式

      1. 二叉树第 i 层至多有2i1个结点(i1)
      2. 高度为 h 的二叉树至多有2h1个结点
      3. 具有 n 个结点的完全二叉树的高度 h 为log2(n+1)log2n+1 , 证明:
      2h11<n2h1
      h1<log2(n+1)h

      h=log2(n+1)

      2h1n<2h
      h1log2n<h

      h=log2n+1

      1. 具有 n 个结点的二叉树,有 n+1 个空链域

        证明:n 个结点的二叉树总共有 2n 个链域,总度数为 n-1,有 n-1 个指针是指向结点的

        所以有 2n-(n-1) = n+1 个指针是空指针

      满二叉树

      一棵高度为h,且含有2h1个结点的二叉树

      完全二叉树

      当且仅当其每个结点都与高度为 h 的满二叉树中编号 1~n 的结点一一对应时,称为完全二叉树

      完全二叉树的编号问题

      如果按层序从1开始编号

      若完全二叉树中有n个结点,则

      如果按层序从0开始编号

      若完全二叉树中有n个结点,则

      平衡二叉树

      树上任一结点的左子树和右子树的深度之差不超过1

      二叉树2.递归遍历

      先序遍历 leetcode144

      中序遍历 leetcode94

      后序遍历 leetcode145

      先序遍历模板

      C++:

      python:

      中序遍历模板:

      和上面代码基本一样,交换它们的顺序:

      后序遍历:

      二叉树3.非递归遍历

      用栈模拟递归的过程

      写出二叉树的非递归遍历很难么?这次让你不再害怕非递归!|二叉树的非递归遍历 | 二叉树的遍历迭代法 | 前序与中(参考视频)

      先序遍历:

      注意:因为栈是先进后出的,先将右子节点入栈,再让左子节点入栈

      C++:

      Python:

      后序遍历:

      前序遍历是按照 中左右 遍历的

      如果把前序遍历代码中

      颠倒顺序, 变成

      遍历顺序变成 中右左

      最后的arr数组进行反转,遍历序列就会变成 左右中 后序遍历序列

      C++:

      Python:

      中序遍历:*

      代码随想录的简洁代码:

      二叉树5:层序遍历

      leetcode102

      二叉树6:翻转二叉树

      leetcode226

      二叉树8:对称二叉树

      leetcode101

      二叉树9:二叉树的最大深度

      leetcode104

      二叉树10:二叉树的最小深度

      leetcode111

      二叉树11:完全二叉树的节点个数

      leetcode222

      方法1:二分查找+位运算

      (思路同力扣官方题解)

      时间复杂度:O(log2n)

      二叉树的深度h=log2(n+1)

      首先需要O(h)的时间确定二叉树的深度

      然后进行二分查找, 每次查找都要访问h个节点, 时间复杂度O(h), 在编号为2h12h1的节点之间进行二分查找(在2h1个节点之间进行二分查找),时间复杂度O(log(2h1))=O(h1).

      所以总的时间复杂度O(h2)=O(log2n)

      因为开辟了长为h的数组,空间复杂度为O(logn)

      方法2:寻找满二叉树

      参考视频

      这个方法利用递归, 更容易写😋

      利用性质:一棵深度为h的满二叉树,节点数量为2h1

      另外, 在C++中, 2n可以写作1 << n

      时间复杂度:O(log2n)

      考虑最坏的情况, 也就是二叉树最大层次只有一个节点的情况, 总共需要递归h层, 每层递归的时间复杂度为O(h), 所以总的时间复杂度为O(h2)=O(log2n)

      空间复杂度:O(log(n))

      在最坏的情况下, 需要递归h层, 故空间复杂度O(log(n))

      二叉树12:平衡二叉树

      leetcode110

      二叉树13:二叉树的所有路径

      leetcode257

      回溯法+dfs

      使用to_string()函数(包含于头文件#include<string>),快速将整数转化为字符串

      二叉树15:左叶子之和

      leetcode404

      这题还挺简单的😏

      二叉树16:找树左下角的值

      leetcode513

      方法1:失败案例(原因:利用对于完全二叉树的节点编号解题,编号过大造成溢出)

      idx的意义是节点在对应完全二叉树中的编号n

      深度h和n的关系为h=log2n+1

      左孩子的编号满足n=n<<1

      右孩子的编号满足n=(n<<1)+1

      方法2: 乖乖用层序遍历,不整花里胡哨的方法才能AC

      方法3:整点花里胡哨的,用回溯法

      利用性质: 在深度优先搜索中,同一层位于左侧的节点总是最先被搜索到

      二叉树17:路径总和

      leetcode112路径总和

      简单题,回溯解决,大佬可以跳过

      leetcode113路径总和II

      还是回溯,上面的代码稍微改动即可

      二叉树18:从中序与后序遍历序列构造二叉树, 从前序与中序遍历序列构造二叉树

      leetcode106从中序与后序遍历序列构造二叉树

      回溯法,有点复杂

      leetcode105 从前序与中序遍历序列构造二叉树

      和上题一样的思路

      二叉树19:最大二叉树

      leetcode654

      二叉树21:合并二叉树

      leetcode617

      一样的回溯思路

      二叉树22:二叉搜索树中的搜索

      leetcode700

      简单题,大佬请跳过

      二叉树23:验证二叉搜索树

      leetcode98

      别小看这题,坑巨多

      二叉树24:二叉搜索树的最小绝对差

      leetcode530

      相当于求二叉树中序遍历序列相邻元素的最小绝对差

      二叉树25:二叉搜索树中的众数

      leetcode501

      采用中序遍历就行

      二叉树26:二叉树的最近公共祖先

      leetcode236

      直接回溯

      二叉树28:二叉搜索树的最近公共祖先

      leetcode235

      和上一题差不多,这题是二叉搜索树,可以利用性质简化

      用指针t从根节点开始采用二分搜索,直到发现t==p||t==q,或者pq分别位于t两侧

      二叉树29:二叉搜索树的插入操作

      leetcode701

      简单题,大佬可跳过

      二叉树30:删除二叉搜索树中的节点

      leetcode450

      回溯专题

      回溯法(backtracking)

      回溯2:组合

      leetcode77

      C++:

      python: 要注意几个global的使用

      回溯4:组合总和III

      leetcode216

      回溯5:电话号码的字母组合

      leetcode17

      方法1: 两层for循环模拟枚举

      方法2:递归回溯

      回溯7:组合总和

      leetcode39

      回溯8:组合总和II

      leetcode40

      回溯9:分割回文串

      leetcode131

      回溯10:复原IP地址

      leetcode93

      回溯11:子集

      leetcode78

      回溯13:子集II

      leetcode90

      回溯14:递增子序列

      leetcode491

      回溯15:全排列

      leetcode46

      回溯16:全排列II

      leetcode47

      方法1:在得到全排列数组后进行整体去重

      60ms,8.8MB

      方法2:在递归的同一层内避免插入相同元素到数组中,有效避免出现重复

      8ms,10.9MB

      回溯19:重新安排行程

      leetcode332

      回溯20:N皇后

      leetcode51

      C++

      python

      回溯21:解数独

      leetcode37

      数独棋盘:

       012345678
      0         
      1         
      2         
      3         
      4         
      5         
      6         
      7         
      8         

      判断是否属于同一个3×3宫:比较x/3*10+y/3的大小

      贪心专题

      贪心2:分发饼干

      leetcode455

      排序 + 双指针 + 贪心

      贪心3:摆动序列

      leetcode376

      python:

      贪心4:最大子数组和

      leetcode53

      这里考虑局部最优解

      从左到右遍历一次nums数组,遍历到第i个元素时,add的含义是选择nums[i]的条件下考虑前i个元素的最大子数组和

      然后用ret记录add的最大值

      C++:

      python:

      贪心6:买卖股票的最佳时机 II

      leetcode122

      动态规划章节也包含了这道题

      方法1:贪心

      相当于截取prices数组中的所有上升子数组,求出它们的首尾元素之差并求和

      C:

      python:

      方法2:奇妙的动态规划

      dfs[i][0]表示第i天结束不持有股票的最大利润pair.first

      dfs[i][1]表示第i天结束持有股票的最大利润pair.second

      C++:一维数组递推

      python:将一维数组压缩为更新两个变量

      贪心7:跳跃游戏

      简单贪心,只需维护bound作为当前能到达的最远位置

      C:

      python:

      贪心8:跳跃游戏II

      leetcode45

      C:

      贪心9:K次取反后最大化的数组和

      leetcode1005

      你可能都没意识到你用了贪心算法, 就不小心AC了

      python:

      贪心11: 加油站

      leetcode134

      难度蹭蹭上涨了

      据说用C++写O(n2)的暴力解法可以通过,感兴趣的可以试试😉

      贪心:

      C++:

      时间复杂度O(n),空间复杂度O(n)

      贪心12:分发糖果

      leetcode135

      方法1:自己的复杂方法

      ratings数组视为一个波, 各个下标处对应的数值为该处波的高度

      一次遍历,找到所有的波谷下标装入队列

      然后从队列逐个取出下标,从波谷向两侧遍历直到到达波峰, 对于严格上升的点糖果数为上一个位置的糖果数+1,平缓的点糖果数为1

      一个位置的糖果数可能被多次计算,取其中的最大值

      C++:

      方法2:大佬们的方法

      正反两次遍历

      python:

      贪心13:柠檬水找零

      leetcode860

      简单模拟就行,用生活经验,有10元就优先用10元找零,5元是万能的

      python:

      贪心14:根据身高重建队列*

      leetcode406

      有点难😭

      搬运自讨论区的精彩解释:https://leetcode.cn/problems/queue-reconstruction-by-height/discussion/comments/1809851

      上了第一节体育课,老师给大家排好了体操的队伍,可是大家脑子都很笨,记不清自己在哪,老师说,你就看前面有几个比自己高的就行!就像这样:

      该上第二节课的时候,大家记住了前面有几个比自己高的,却还是忘记了怎么排,老师见状让学生从高到低排好队,身高一样的,比自己高的越多,越往后面站,像这样:

      每次让最高的学生出来找自己的位置,第一个高个子[7,0]自然站到了第一个位置:

      而第二个高个子[7,1]知道有一个人大于等于自己的身高,站在了第一个人身后:

      第三个人[6,1]想了想,有一个人比自己高,那自己肯定站在第二位,于是就插队,现在也站到了第一个人身后:

      第四个人[5,0]想了想,没人比自己高,那自己肯定站在第一位,于是就插队,站到了队头:

      第五个人[5,2]想了想,有两个人比自己高,于是就插队,站到了第二个人后面,也就是第三个位置:

      第六个人[4,4]看了看眼前的队伍,比自己高的人都在里面,他安心的数着前面有四个人比自己高,心安理得的站到了第四个人身后:

      其实这道题的大概思路就是这样,只有先让身高高的先进入队伍,后面身高低的才能根据前面高的来找自己的位置

      C++:

      贪心17:用最少数量的箭引爆气球*

      leetcode452

      很经典的区间问题

      贪心18:无重叠区间

      leetcode435

      首先按照右边界的坐标从小到大排序,如果右边界坐标相等,就按照左边界从大到小排序

      然后从左到右遍历, 对于每个被遍历到的区间,都删除掉它后面所有与之相交的区间

      被删除的区间不会再参与遍历

      几种已经排好序的样例如下(带x的被删除掉)

      C++:

      贪心19:划分字母区间

      leetcode763

      和上面两题相似,也是区间重叠问题

      C++: 自己的糟糕代码

      大佬的优雅代码(搬运自https://leetcode.cn/problems/partition-labels/discussion/comments/31356):

      贪心20:合并区间

      leetcode56

      贪心22:单调递增的数字

      leetcode738

      方法1:从左到右遍历(作者的笨办法)

      将n各个位填入数组(字符串也行),从左到右遍历:

      当发现当前位数字比前一位数字小时,就开始修改字符串,修改完字符串就能返回结果

      修改规则为:前一位数字减1,当前位数字及之后所有位的数字一律为9

      例如6328,遍历到3时,将前1位减1得5,后面一律为9,得5999

      考虑一种情况,n=332,遍历到下标2时发现数字比前一位小,将下标为1处的3改为2,后面置为9后,得329不符合题意,这说明还需要另外加一个循环从下标为1处向前遍历,如果当前位置数字比前一位小了,就把当前位置数字置为9,前一位数字减一,处理后数字变为299

      C++: 0ms,59MB

      方法2:从右往左遍历(大佬的优雅方法)

      C++: 4ms,5.9MB

      大佬虽然优雅,但耗时有点长

      贪心23:监控二叉树

      leetcode968

      val: 1->安装监控 2->接受下方节点监控 3->接受上方节点监控

      图论专题

      最小生成树:连接所有节点的最小费用

      leetcode1584

      本题为边稠密图,更适合普里姆算法

      prim普里姆算法

      从某一个顶点开始构建生成树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止

      SysuGLM的解释:

      Prim 算法是一种用于解决无向图最小生成树问题的贪心算法。它的基本思想是从一个顶点开始,不断地寻找与当前生成树距离最近的顶点,将其加入到生成树中,直到所有顶点都加入到生成树中为止。该算法是由捷克数学家 Vojtěch Jarník 于 1930 年发现的,并在 1957 年由美国计算机科学家 Robert C. Prim 重新发现,因此得名 Prim 算法。 以下是 Prim 算法的基本步骤:

      1. 初始化一个空的最小生成树 T。
      2. 任选图中一个顶点 v,将其加入到 T 中。
      3. 在图中寻找距离 T 最近的顶点 u,将边 (u, v) 加入到 T 中。
      4. 重复步骤 3,直到所有顶点都加入到 T 中。
      5. 得到的 T 即为原图的最小生成树。

      Prim 算法的时间复杂度取决于具体的实现方式。最简单的实现方式是用邻接矩阵表示图,其时间复杂度为 O(n^2),其中 n 为图的顶点数。使用优先队列和邻接表可以进一步优化算法的性能,将时间复杂度降低到 O(nlogn)。

      设总共V个节点,时间复杂度O(V2), 适用于边稠密图

      leetcode1584通过,68ms, 9.84MB

      对于本题,有n个顶点,时间复杂度O(n2)

      Kruskal算法

      SysuGLM的解释:

      Kruskal 算法是一种贪心算法,用于求解连通网的最小生成树。具体步骤如下:

      1. 将所有的边按照权重从小到大排序。
      2. 初始化一个空集合,用于存放已选择的边。
      3. 按照排序后的顺序依次遍历每条边,检查当前边的两个顶点是否属于同一个连通分量(可以使用并查集数据结构进行快速判断)。如果不属于同一个连通分量,那么将这条边加入到已选择的边的集合中,并合并这两个顶点所在的连通分量;如果已经属于同一个连通分量,那么跳过这条边。
      4. 当已选择的边的数量等于顶点数减一时,算法结束。此时已选择的边构成了连通网的最小生成树。 这种算法的时间复杂度为 O(ElogE),其中 E 是边的数量。

      该算法利用Quick Find版本的并查集, 有关并查集Quick Find和Quick Union版本的区别, 参考本文。如果利用Quick Union版本的并查集,会超时

      leetcode1584通过,1808ms, 24.37MB

      对于本题,共n个顶点,每两个顶点之间都有边连接,|E|=n2,所有时间复杂度是O(n2logn)

      最短路径问题:

      image-20230817173317209

      图出自王道考研数据结构

      参考视频【王道计算机考研 数据结构】

      例题:

      BFS算法比较基础,且只能处理不带权的图,这里就不介绍了

      Dijkstra算法

      当前算法适用于稠密图

      求带权图的最短路径长度,局限是不能处理负权图

      对于一系列顶点V0,V1,...,Vn1组成的有向带权图,求V0到各个顶点的最短路径长度

      初始化三个数组:

      C++

      leetcode743通过,92ms,36.5MB

      python

      leetcode743通过,72ms,17.6MB

      复杂度分析

      节点总数为|V|,要遍历一次所有顶点,对于每一次遍历,要更新与当前节点直接相连,并且final值为false的全部节点的dist值,该过程遍历|V|次;还要找出从当前节点出发,下一个最近的节点,遍历|V|

      时间复杂度O(|V|2),空间复杂度O(|V|2).(邻接矩阵占用的空间)

      当前算法只能求一个顶点到其他所有顶点的最短路径,如果需要求所有顶点到其他顶点的最短路径,则需要将该算法循环|V|次,总的时间复杂度O(|V|3)

      Dijkstra算法优化:使用小根堆priority_queue

      当前算法适用于稀疏图

      复杂度分析

      设顶点数为|V|,边数为|E|,小根堆的最大长度为|E|,小根堆的插入和删除时间复杂度为O(log|E|),总共进行|E|次遍历,总时间复杂度O(|E|log|E|)

      dist数组占用空间O(|V|),vec数组和小根堆占用空间O(|E|),总空间复杂度O(|E|+|V|)

      Floyd算法

      Floyd算法更加通用,可以解决带负权值的图,但前提是最短路径存在

      3
      4
      -9
      A
      B
      C

      如上图所示,要求A到C的最短路径,如果选择的路径是沿着箭头一直前进,每循环一圈路径长度减2,A到C的路径可以无穷小,不存在最短路径

      leetcode743通过,160ms,37MB

      复杂度分析

      该过程相当于对一个三维数组的动态规划(在内存使用上可以只使用二维数组),时间复杂度O(|V|3),空间复杂度O(|V|2)

      Bellman-ford算法

      (引用自百度百科)

      贝尔曼-福特算法与迪科斯彻算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。在两个算法中,计算时每个边之间的估计距离值都比真实值大,并且被新找到路径的最小长度替代。 然而,迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点,然后对其的出边进行松弛操作;而贝尔曼-福特算法简单地对所有边进行松弛操作,共|V|1

      次,其中|V|是图的点的数量。在重复地计算中,已计算得到正确的距离的边的数量不断增加,直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

      CSDN Bellman-ford算法

      leetcode743通过,152ms,35.7MB

      时间复杂度O(|V||E|),其中|V|是顶点数,|E|是边数

      SPFA算法

      SPFA算法是对Bellman-ford算法的优化

      shortest path faster algorithm

      参考文献CSDN SPFA算法,画图详细解释了该算法,适合小白

      leetcode743通过,84ms,39MB

      洛谷P3371 【模板】单源最短路径(弱化版)通过

      SPFA的复杂度大约是O(kE),k是每个点的平均进队次数(一般的,k是一个常数,在稀疏图中小于2)。

      引用出处

      拓扑排序

      参考王道考研数据结构

      AOV网(Activity On Vertex Network):用顶点表示活动的网

      用DAG图(有向无环图)表示一个工程,顶点表示活动,有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行

      准备厨具
      打鸡蛋
      切番茄
      买菜
      洗番茄
      下锅炒
      吃番茄炒蛋

      表示“番茄炒蛋工程”的AOV网

      拓扑排序的一种结果:

      准备厨具
      买菜
      洗番茄
      切番茄
      打鸡蛋
      下锅炒
      吃番茄炒蛋

      拓扑排序的实现:

      1. 从AOV网中选择一个没有前驱(入度为0)的顶点并输出
      2. 在网中删除该顶点和所有以它为起点的有向边
      3. 重复步骤1和2直到当前的AOV网为空当前网中不存在无前驱的顶点(说明有回路)为止

      出现回路的情况:

      洗番茄
      切番茄
      下锅炒
      吃番茄炒蛋

      当前所有顶点的入度>0,说明原图存在回路

      课程表

      leetcode207

      方法1:BFS

      方法2:DFS

      参考力扣官方题解

      课程表II

      leetcode210

      方法1:BFS

      方法2:DFS

      图论1:统计点对的数目

      leetcode1782

      参考灵神的题解

      利用算法:哈希表6.9:两数之和 II - 输入有序数组

      图论2:课程表IV

      leetcode1462

      Floyd算法:

      python

      广度优先搜索+记忆化

      C++

      图论3:所有可能的路径

      leetcode797

      dfs搜索所有路径

      图论4:岛屿数量

      leetcode200

      dfs

      图论5:岛屿的最大面积

      leetcode695

      图论6:飞地的数量

      leetcode1020

      相似题目:统计封闭岛屿的数目

      leetcode1254

      图论9:太平洋大西洋水流问题

      leetcode417

      从四边形边界开始dfs搜索,搜索的条件为下一个待搜索的位置高度比当前所在位置高

      共进行二轮搜索,第一轮从最左列和最上行出发,第二轮从最下行和最右列出发

      最后返回两轮都被搜索到的下标

      图论10:最大人工岛

      leetcode827

      使用并查集

      第一次遍历整个矩阵中值为1的部分,连接所有岛屿

      第二次遍历整个矩阵中值为0的部分,考虑将当前遍历的点变为岛屿,可以连接的岛屿面积有多大

      时间复杂度O(n2)

      图论11:单词接龙

      leetcode127

      利用BFS搜索可能的单词转换路径

      挑战:用C语言解决

      图论12:钥匙和房间

      leetcode841

      BFS

      图论16:冗余连接

      leetcode684

      使用并查集,从前到后遍历所有边,连接当前边的两个结点,直到当前两个结点的父结点相同

       

      动态规划专题

      代码随想录的刷题顺序:

      动态规划3:爬楼梯

      点击跳转

      动态规划4:使用最小花费爬楼梯

      点击跳转

      动态规划6:不同路径

      leetcode62

      方法1:数学,利用组合数直接计算Cm+n2m1

      C:

      方法2:动态规划

      python:

      动态规划7:不同路径II

      leetcode63

      C:

      python:

      动态规划8:整数拆分

      点击跳转

      动态规划9:不同的二叉搜索树

      点击跳转

      0-1背包系列 13~17

      动态规划13:分割等和子集

      点击跳转

      动态规划14:最后一块石头的重量II

      点击跳转

      动态规划16:目标和

      点击跳转

      动态规划17:一和零

      点击跳转

      完全背包系列 19~26

      动态规划19:零钱兑换II

      点击跳转

      动态规划21:组合总和IV

      点击跳转

      动态规划23:零钱兑换

      点击跳转

      动态规划24:完全平方数

      点击跳转

      动态规划26:单词拆分

      leetcode139

      方法1:BFS(广度优先搜索)+记忆化搜索

      方法2:完全背包

      (出自代码随想录)

      单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。

      拆分时可以重复使用字典中的单词,说明就是一个完全背包!

      打家劫舍问题29-31

      动态规划29:打家劫舍

      点击跳转

      动态规划30:打家劫舍II

      点击跳转

      动态规划31:打家劫舍III

      leetcode337

      每个节点都有偷和不偷两种选择,用pair对组存储两种情况下的最大收益

      如果偷了当前节点,则左右节点都不能偷,只有一种情况

      如果不偷当前节点,有四种情况:偷左右节点、偷左不偷右、偷右不偷左、左右都不偷

      股票问题32-38

      动态规划32.买卖股票的最佳时机

      leetcode121

      方法1:贪心

      用双指针实现,左指针取最小值,右指针取最大值,差值就是最大利润

      C:

      方法2:动态规划

      维护两个变量,分别是have今天结束后 持有股票的最大利润,notHave今天结束后 不持有股票的最大利润

      python:

      动态规划34.买卖股票的最佳时机II

      详见贪心章节

      总结一下32题和34题的动态规划区别

      32题的特点是只能买一次

      34题的特点是无限次购买:

      除了标黄的部分,两题的递推公式都是一样的

      对比代码:

      32题:

      tp1=max(have,-prices[i])

      tp2=max(notHave,have+prices[i])

      34题:

      tp1=max(have,notHave-prices[i])

      tp2=max(notHave,have+prices[i])

      动态规划35.买卖股票的最佳时机III

      leetcode123

      本题是下一题的削减版,对应下一题的k=2情况

      动态规划:

      注意,如果你用的是C++,-inf不能简单地用INT_MIN代替,因为动态规划过程中可能会涉及到对INT_MAX减去一个正数的操作

        33500314
      0第一次持有-3-3-300000
      1第一次卖出-inf0222334
      2第二次持有-inf-inf-522222
      3第二次卖出-inf-inf-inf-52556

      python:

      C++: 实现上有些区别,比如将每次持有和卖出的两种情况压缩到对组内

      动态规划36:买卖股票的最佳时机IV

      leetcode188

      解析见上一题

      python:

      C++:

      动态规划37:买卖股票的最佳时机含冷冻期

      leetcode309

      方法1:划分出三种状态

        12302
      0持有股票-1-1-111
      1保持卖出股票00122
      2卖出股票-inf12-13

      python:

      方法2:两种状态(带下划线的初始化要特殊考虑)

        12302
      0不持有股票01223
      1持有股票-1-1-111

      python:记忆化递归

      C++:

      动态规划38:买卖股票的最佳时机含手续费

      leetcode714

      fee=2

        132849
      0不持有股票000558
      1持有股票-3-3-3-3-1-1

      python:递归

      C++:递推

      子序列问题

      动态规划41:最长递增子序列

      leetcode300

      n为nums数组长度

      方法1:动态规划

      dp[i]表示以i为结尾的最长子序列

      时间复杂度O(n2)

      方法2:贪心+二分查找

      g[i]为长度为i+1的子序列末尾元素的最小值

      贪心+二分查找,时间复杂度O(nlog(n))

      g数组性质:1、严格递增 2、只更新一个位置,更新的位置是第一个>=nums[i]的数的下标

      动态规划42:最长连续递增序列

      leetcode674

      简单题,大佬们可以跳过

      动态规划43:最长公共子序列

      leetcode718

      动态规划44:最长公共子序列

      点击跳转

      动态规划45:不相交的线

      leetcode1035

       1052152
      2001111
      5011122
      1011222
      2012223
      5012233
      dp[i][j]={dp[i1][j1]+1,nums1[i]=nums2[j]max{dp[i1][j],dp[i][j1]},nums1[i]nums2[j]

      python:

      动态规划46:最大子序和

      leetcode53

      代码随想录:

      dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]

      1. 确定递推公式

      dp[i]只有两个方向可以推出来:

      • dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和
      • nums[i],即:从头开始计算当前连续子序列和

      一定是取最大的,所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

      C++

      python

      动态规划47:判断子序列

      leetcode392

      本题和45:不相交的线很像

      动态规划48:不同的子序列

      leetcode115

      dp(i,j)表示 字符串t的前i+1个字母(t[0:i+1]) 在 字符串s的前j+1个字母(s[0:j+1])的子序列中 出现的次数

      dp(i,j)s[j]babgbag
      t[i]11111111
      b01122333
      a00111144
      g00001115
      dp(i,j)={dp(i,j1)+dp(i1,j1),t[i]=s[j]dp(i,j1),t[i]s[j]

      解析:

      t[i]!=s[j]时,当前的两个字符不匹配,dp(i,j)=dp(i,j-1)t[0:i+1]和s[0:j+1]的匹配问题可以转化为t[0:i+1]s[0:j]的匹配问题。

      举个例子,s=“bab”和t=“ba”不同子序列数,等价于s=“ba”和t=“ba”的不同子序列数,因为前者两个串末尾不同,可以看作s1新增的末尾字母b对不同子序列数不构成影响

      t[i]==s[j]时,当前的两个字符匹配,dp(i,j)=dp(i,j-1)+dp(i-1,j-1)

      举个例子,s=“babgba”和t=“ba”的不同子序列数,等于s=“babgb”和g=“ba”的子序列数,加上s=“babgb”,t=“b”的子序列数。

      python:(记忆化递归)

      C++

      Javascript

      动态规划49:两个字符串的删除操作

      leetcode583

      这题本质上和动态规划43:最长公共子序列相同

      python:

      C

      动态规划50:编辑距离

      点击跳转

      动态规划52:回文子串

      leetcode647

      中心扩散解法:时间复杂度O(n2)

      动态规划解法也是O(n2),就懒得写了

      动态规划53:最长回文子序列

      leetcode516

      dp(i,j)表示在区间[i,j]内最长回文子序列的长度

      动态规划54:切披萨的方案数

      leetcode1444

      考察二维差分和三维动态规划

      此题定义了pi数组,pi[i][j]意义为pizza数组中左上角(i,j)到右下角(row-1,col-1)矩形区域内苹果总数

      dp(i,j,c)的意义为左上角(i,j)到右下角(row-1,col-1)矩形区域切c刀的方案总数


      灵神的刷题顺序:

      动态规划:从记忆化搜索到递推

      动态规划入门:从记忆化搜索到递推【基础算法精讲 17】(参考视频)

      198打家劫舍

      leetcode链接

      维护一个数组vec[i]表示从前i个房子中能获得的最大金额和

      vec[i]=max(vec[i-2]+nums[i],vec[i-1])

      如果选择偷当前第i间的,最优收益是偷前i-2间的收益加上本间的收益

      如果不偷当前第i间,最优收益是偷前i-1间的收益

      C++:

      Python:

      (灵神的递归做法)

      JavaScript:

      课后作业:

      70. 爬楼梯

      leetcode链接

      vec[i]表示到达第i级楼梯至少需要几步

      一次可以跨1或2阶,故vec[i]=vec[i-1]+vec[i-2]

      C:

      python:

      746. 使用最小花费爬楼梯

      leetcode链接

      用数组li[k]表示到达第k级的最小花费

      因为出发没有花费,li[0]=li[1]=0

      li[k]=min(li[k-1]+cost[k-1],li[k-2]+cost[k-2])

      python:

      2466.统计构造好字符串的方案数

      leetcode链接

      dfs[i]表示长度为i的字符串的好字符串数目

      dfs[0]=1,dfs[k]=0(k<0)

      dfs[i]=dfs[i-zero]+dfs[i-one]

      为了C++防溢出(python防爆内存),需要在计算过程中对m=109+7取余

      C++:

      python:

      213.打家劫舍 II

      leetcode链接

      本题和打家劫舍类似,可以套用上次的代码,因为首尾相接,从[0,n]间房获得的最大收益等价于

      max{从[0,n-1]间房获得的最大收益,从[1,n]间房获得的最大收益}

      C:

      python:

      Javascript:

      拆分类动态规划

      343.整数拆分

      leetcode链接

      参考视频

      解法1:动态规划

      定义dp[i]是整数i拆分后相乘能得到的最大整数(i>=2)

      dp[i]=max(j*(i-j),j*dp[i-j]) (1<=j<i)

      解法2: 数学

      粘贴自讨论区:

      If an optimal product contains a factorf >= 4, then you can replace it with factors2and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you'd only use it for n=2 and n=3, where it's needed).

      For the rest I agree, 3*3 is simply better than2*2*2, so you'd never use 2more than twice.

      C:

      96.不同的二叉搜索树

      leetcode链接

      参考视频

      C++: 数组动规

      python: 记忆化递归

      0-1背包和完全背包

      01背包:416. 分割等和子集 474. 一和零 494. 目标和 879. 盈利计划 1049. 最后一块石头的重量 II 1230. 抛掷硬币

      完全背包:1449. 数位成本和为目标值的最大数字 322. 零钱兑换 518. 零钱兑换 II 279. 完全平方数


      0-1背包 完全背包 基础算法精讲 18(视频链接)

      494. 目标和(0-1背包)

      leetcode链接

      解法1. 回溯(暴力)解法:可以1952ms踩线通过

      C++:

      解法2:灵神的0-1背包记忆递归模板

      记忆递归模板

      示例出自CSDN

      有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

      为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8

      i(物品编号)1234
      w(体积)2345
      v(价值)3456

      上述例子的dp数组打印: (dfs(i,c)=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]))

      dfs012345678
      -1000000000
      0003333333
      1003447777
      2003457899
      30034578910

      image-20230705180715673

      灵神0-1背包递归模板(python):

      上述模板的C++版本:

      本题需要对上述模板进行变形,变形方式如下图

      image-20230705202036945

      解题

      python:

      C++:

      解法3: 数组递推的动态规划解法

      本题相当于v[i]=1,w[i]=nums[i]的情况

      s=(i=0nnums[i])target

      本题等价于在nums中任意取几个数相加,满足和等于s2,求任意取几个数相加的方法总数

      例如nums=[1,2,3,1,2],target=-1

      只需在nums中任意取几个数相加,满足和等于5

      arr[i][j]012345
      -1100000
      0(1)110000
      1(2)111100
      2(3)111211
      3(1)122332
      4(2)123555

      arr[i][j]表示只考虑numsi个元素时,相加得到j的最多方法数

      arr[i][j]=arr[i-1][j]+arr[i-1][j-nums[i]]

      注意坑: s为奇数或s<0都应当返回0

      C++:

      python:

      322. 零钱兑换

      leetcode链接

      这是一个完全背包问题

      举例:

      arr[i][j]表示当前状态下所需最少硬币数

      arr[i][j]=min(arr[i-1][j],arr[i][j-coins[i-1]]+1)i1

      icoins01234567
      0 0
      1101234567
      2201122334
      3301112223
      4401111222
      5501111122

      C++:二维数组递推

      Python:(记忆化递归)

      优化:压缩为一维数组

      C++

      python:

      课后作业:

      416. 分割等和子集

      leetcode链接

      对于nums=[1,5,11,5]的测试用例

       01234567891011
       100000000000
      1110000000000
      5110001100000
      11110001100001
      5110002200012

      arr(i,c)=arr(i-1,c-num[i])+arr(i-1,c)

      完成第5行时最后一列非0,可以返回True

      记忆化递归

      python:

      代码中k从小到大进行枚举,相当于按照nums数组由短到长枚举,很多数组只考虑前面一小段就符合条件,这样可以减少递归层级,防止超出内存限制

      正常的二维数组动规:

      C++:

      Javascript:

      压缩为一维数组:

      Python:使用临时数组

      C++:carl模板的倒序递推

      注意:本题如果用C++,只能用递推公式dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);

      而不能用dp[j]+=dp[j-nums[i]],因为后者dp[i]的含义是当前枚举到的数中加和为i的所有组合总数,会溢出

      分割等和子集问题的变换:

      1049.最后一块石头的重量II

      leetcode链接

      对于stones=[a1,a2,,an]

      可以找到一种分割子集的方法,使两个子集[b1,b2,,bi][c1,c2,,cj]的和相差最小,相差记为s

      b1+b2++bi=c1+c2++cj+s

      (b1,b2,,bi,c1,c2,,cjstones)

      s就是最后石头的最小可能重量

      最后会把石头分成两堆,重量分别为addsu-add(add<=su-add)

      add的理论最大值为su//add(//是整除),只需让addsu//add开始枚举递减,直到找到一种石头组合是部分总重量为add

      对应的最后一块石头的重量为su-add-add=su-2*add

      python:

      C++:

      279. 完全平方数

      leetcode链接

      测试用例n=12:

      arr=[1,4,9]

      dfs0123456789101112
       0
      10123456789101112
      40123123423453
      90123123421233

      dfs(i,c)=min(dfs(i-1,c),dfs(i,c-arr[i])+1)

      递归会爆内存,所以只贴压缩为一维数组的递推代码

      C++:

      python:

      518. 零钱兑换 II

      leetcode链接

       012345
       100000
      1111111
      2112233
      5112234

      vec[i][j]=vec[i-1][j]+vec[i][j-coins[i-1]];

      二维数组法

      C++:

      (记忆化)递归法

      python:

      压缩为一维数组:

      C++:

      python:

      377.组合总和IV

      leetcode链接

      与上题几乎一样,区别使上一题求组合数,不考虑顺序,本题求排列数,考虑顺序

      只需交换两个for循环的顺序

      dp数组表:(nums=[1,2,3],target=4)

       01234
       10000
      111124
      211236
      311247

      二维数组:

      dp(i,c)={dp(i1,c),c<nums[i]dp(i1,c)+dp(nums.size()1,cnums[i]),cnums[i]

      一维数组:

      474. 一和零

      leetcode链接

      这是一个0-1背包问题,区别是背包容量是一个二维的情况,即要同时考虑0和1的容量

      w0[i]表示str[i]含有0的个数

      w1[i]表示str[i]含有1的个数

      dfs(i,c,d)表示只考虑前i个字符串,0的剩余容量为c,1的剩余容量为d的情况下,字串的最大长度

      dfs(i,c,d)=max{dfs(i-1,c,d),dfs(i-1,c-w0[i],d-w1[i])+1}

      方法1:灵神模板记忆化递归

      python:

      C++:

      方法2:三维数组动规

      C++:

      879.盈利计划

      leetcode链接

      最长公共子序列

      最长公共子序列 编辑距离【基础算法精讲 19】 (参考视频)

      1143.最长公共子序列

      leetcode链接

      image-20230706112658119

      可以得到递推式:

      image-20230706112721998

      可以证明,简化后结果为

      dfs(i,j)={dfs(i1,j1)+1(s[i]=t[j])max{dfs(i1,j),dfs(i,j1)}(s[i]t[j])

      python:

      72. 编辑距离

      leetcode链接

      dp(i,j)={min{dp(i1,j),dp(i,j1),dp(i1,j1)}+1,word1[i]word2[j]dp(i1,j1),word1[i]=word2[j]
      dp(i,j)ros
      0123
      h1123
      o2212
      r3222
      s4332
      e5443

      课后作业:

      583. 两个字符串的删除操作

      leetcode链接

      点击跳转

      712. 两个字符串的最小ASCII删除和

      leetcode链接

      dp(i,j)={dp(i1,j1)+ascii(s1[i]),s1[i]=s2[j]max{dp(i1,j),dp(i,j1)},s1[i]s2[i]

      1458. 两个子序列的最大点积

      leetcode链接

        30-6
       0000
      20666
      10666
      -206618
      50151518
      dp(i,j)=max{dp(i1,j1)+nums1[i]nums2[j],dp(i1,j),dp(i,j1)}

      97. 交错字符串

      leetcode链接

      三维dp

      单调栈专题

      单调栈1:每日温度

      leetcode739

      C++:

      python:

      单调栈2:下一个更大元素I

      leetcode496

      原理和上一题一样,时间复杂度为O(nums1.length + nums2.length)